package 学习;

import java.util.Arrays;

/**
 * Keafmd
 *
 * @ClassName: CountSort
 * @Description: 计数排序
 * @author: 牛哄哄的柯南
 * @date: 2021-06-24 11:31
 */
public class CountSort {

    public static void countSort(int[] arr) {
        countSort(arr, true);
    }

    public static void countSort(int[] arr, boolean ascending) {
        if (arr == null || arr.length == 0) {
            return;
        }
        // 找出最大、最小值
//        int min = arr[0], max = arr[0];
//        for (int i = 0; i < arr.length; i++) {
//            if (arr[i] < min) {
//                min = arr[i];
//            }
//            if (arr[i] > max) {
//                max = arr[i];
//            }
//        }
        int min = Arrays.stream(arr).min().getAsInt();
        int max = Arrays.stream(arr).max().getAsInt();

        //建立一个用于计数的数组
        int d;
        d = min;
        int[] count_map = new int[max - min + 1];
        for (int i = 0; i < arr.length; i++) {
            count_map[arr[i] - d]++;
        }

        int k = 0;
        if (ascending) {
            for (int i = 0; i < arr.length; ) {
                if (count_map[k] > 0) {
                    arr[i] = k + d;
                    i++;
                    count_map[k]--;
                } else {
                    k++;
                }
            }
        } else {
            for (int i = arr.length - 1; i >= 0; ) {
                if (count_map[k] > 0) {
                    arr[i] = k + d;
                    i--;
                    count_map[k]--;
                } else {
                    k++;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] nums = {12, 4, 25, 47, 58, 34, 25, 9, 99, 26, 1, -13, 162, 10093, -66, -1};
        int[] temparr;
        //测试计数排序
        System.out.println("测试计数排序:");
        temparr = nums.clone();
        CountSort.countSort(temparr);
        //逆序排序
        //CountSort.countSort(temparr,false);
        System.out.println(Arrays.toString(temparr));
    }
}